package BF_DP;

public class Test3 {
    public static int getWay(int x,int y,int k){
        return process(x,y,k);
    }

    //潜台词:从(0,0)位置出来的情况下,要去往(x,y)位置,但是必须跳step步,返回方法数
    public static int process(int x,int y,int step){
//        处理越界的情况
        if (x < 0 || x > 8 || y < 0||y > 9){
            return 0;
        }
        if (step == 0){//处理跳完个数的情况
            return (x==0&&y==0)?1:0;
        }
        //不越界,也有步数可以跳
        return process(x-1,y+2,step-1)
                +process(x+1,y+2,step-1)
                +process(x+2,y+1,step-1)
                +process(x+2,y-1,step-1)
                +process(x+1,y-2,step-1)
                +process(x-1,y-2,step-1)
                +process(x-2,y-1,step-1)
                +process(x-2,y+1,step-1);

    }
    //用动态规划该
    public static int dpWays(int x,int y,int step){
    //虽然我能理解为成一个柱形,上层结果是由下层的完全推导出来的
        if (x < 0 || x > 8 || y < 0||y > 9){
            return 0;
        }
        int[][][] dp = new int[9][10][step+1];
        dp[0][0][0] = 1;
        for (int h = 0; h < step; h++) {
            for (int r = 0; r < 9; r++) {
                for (int c = 0; c < 10; c++) {
                    dp[r][c][h] += getValue(dp,r-1,c+2,h-1);
                    dp[r][c][h] += getValue(dp,r+1,c+2,h-1);
                    dp[r][c][h] += getValue(dp,r+2,c+1,h-1);
                    dp[r][c][h] += getValue(dp,r+2,c-1,h-1);
                    dp[r][c][h] += getValue(dp,r+1,c-2,h-1);
                    dp[r][c][h] += getValue(dp,r-1,c-2,h-1);
                    dp[r][c][h] += getValue(dp,r-2,c-1,h-1);
                    dp[r][c][h] += getValue(dp,r-2,c+1,h-1);
                }
            }
        }
        return dp[x][y][step];
    }
    public static int getValue(int[][][] dp,int row,int col,int step){
    if (row < 0 || row > 8|| col<0||col>9){
//            如果越界则0
        return 0;
    }
    return dp[row][col][step];
    }
}
